{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## _*Using Qiskit Aqua for the vertex-cover problems*_\n",
    "\n",
    "A vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. The goal of NPC problem is to minimize the size of the vertex cover. \n",
    "\n",
    "We will go through two examples to show:\n",
    "1. How to run the optimization\n",
    "2. How how to run the optimization with the VQE."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### The problem and the brute-force method\n",
    "\n",
    "The problem is as follows. the graph is in the adjacent matrix form."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 0.  5. -4.]\n",
      " [ 5.  0.  0.]\n",
      " [-4.  0.  0.]]\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "from qiskit import BasicAer\n",
    "from qiskit.optimization.applications.ising import vertex_cover\n",
    "from qiskit.aqua.algorithms import NumPyMinimumEigensolver\n",
    "from qiskit.optimization.applications.ising.common import random_graph, sample_most_likely\n",
    "\n",
    "np.random.seed(100)\n",
    "num_nodes = 3\n",
    "w = random_graph(num_nodes, edge_prob=0.8, weight_range=10)\n",
    "print(w)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The brute-force method is as follows. Basically, we exhaustively try all the binary assignments. In each binary assignment, the entry of a vertex is either 0 (meaning the vertex is not in the cover) or 1 (meaning the vertex is in the cover). We print the binary assignment that satisfies the definition of the vertex cover and corresponds to the minimial size. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Size of the vertex cover 1\n"
     ]
    }
   ],
   "source": [
    "def brute_force():\n",
    "    # brute-force way\n",
    "    def bitfield(n, L):\n",
    "        result = np.binary_repr(n, L)\n",
    "        return [int(digit) for digit in result]  # [2:] to chop off the \"0b\" part\n",
    "\n",
    "    L = num_nodes\n",
    "    max = 2**L\n",
    "    minimal_v = np.inf\n",
    "    for i in range(max):\n",
    "        cur = bitfield(i, L)\n",
    "\n",
    "        cur_v = vertex_cover.check_full_edge_coverage(np.array(cur), w)\n",
    "        if cur_v:\n",
    "            nonzerocount = np.count_nonzero(cur)\n",
    "            if nonzerocount < minimal_v:\n",
    "                minimal_v = nonzerocount\n",
    "\n",
    "    return minimal_v\n",
    "\n",
    "size = brute_force()\n",
    "print('Size of the vertex cover', size)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "qubit_op, offset = vertex_cover.get_operator(w)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Part I: Run the optimization"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1 0 0]\n",
      "Size of the vertex cover 1\n"
     ]
    }
   ],
   "source": [
    "algo = NumPyMinimumEigensolver(qubit_op)\n",
    "result = algo.run()\n",
    "\n",
    "x = sample_most_likely(result.eigenstate)\n",
    "sol = vertex_cover.get_graph_solution(x)\n",
    "print(sol)\n",
    "print('Size of the vertex cover', np.count_nonzero(sol))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Part II: Run the optimization with the VQE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Size of the vertex cover 1\n"
     ]
    }
   ],
   "source": [
    "from qiskit.aqua import aqua_globals\n",
    "from qiskit.aqua.algorithms import VQE\n",
    "from qiskit.aqua.components.optimizers import SPSA\n",
    "from qiskit.circuit.library import TwoLocal\n",
    "\n",
    "aqua_globals.random_seed = 100\n",
    "\n",
    "optimizer = SPSA(maxiter=200)\n",
    "var_form = TwoLocal(qubit_op.num_qubits, ['ry', 'rz'], 'cz', reps=3)\n",
    "vqe = VQE(qubit_op, var_form, optimizer)\n",
    "\n",
    "backend = BasicAer.get_backend('qasm_simulator')\n",
    "result = vqe.run(backend)\n",
    "\n",
    "x = sample_most_likely(result.eigenstate)\n",
    "sol = vertex_cover.get_graph_solution(x)\n",
    "print('Size of the vertex cover', np.count_nonzero(sol))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
